import javax.sound.sampled.LineEvent;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:张熳
 * Date:2025-11-15
 * Time:1:26
 */
//从前序与中序遍历序列构造二叉树
//给定两个整数数组preorder和inorder，其中preorder是二叉树的先序遍历，inorder是同一棵树的中序遍历，
//请构造二叉树并返回其根节点。
//思路：前序遍历确定根；中序遍历中，找到根节点的位置，确定左子树和右子树。前序遍历和中序遍历构造二叉树的方式是先创建左子树，再创建右子树。
//在buildTreeChild方法中，首先我们需要一个preIndex成员变量，用来标记前序遍历序列中数据的下标(它必须是成员变量，不能作为一个方法参数传参，否则在
//每次递归传递时，preIndex变量都会重新从0开始)，根据这个下标创建二叉树的根节点root，接着需要一个参数rootIndex，用来标记中序遍历序列中作为根节点
//的节点下标位置：写一个方法findVal，用来寻找中序序列中等于root的节点的下标位置，如果找到，返回它的下标，即rootIndex，如果没有找到啊，返回-1。
//创建完根节点root和找到它的下标rootIndex后，preIndex要++往后走。
//然后根据rootIndex可以确定它的左边序列为左子树，右边序列为右子树，用inBegin标记每次递归时中序遍历序列的起始位置，用inEnd来标记每次递归时
//中序遍历序列的结束位置：在递归创建二叉树的左子树时，在它创建完root和确定完rootIndex的位置后，inBegin标记的位置不变，而inEnd标记的是rootIndex
//的前一个位置，该位置就是左子树序列的结束位置，即rootIndex-1;而在递归创建右子树时，是inEnd的位置不变，而inBegin标记的是rootIndex的后一个位置，
//该位置就是右子树序列的起始位置，即rootIndex+1。在递归过程中，如果出现inBegin>inEnd的情况，则说明当前的root已经没有子树了，返回null（由于
//前序遍历是按照 根-左子树-右子树 方式遍历的，前面说过，在遍历左子树时，inEnd=rootIndex-1，但是此时的root是一个叶子节点，rootIndex、inBegin
//、inEnd都应该等于该root的位置，所以，如果还按照非叶子节点时求inEnd的逻辑，那么求完之后会出现inBegin>inEnd，该情况就代表当前root是叶子节点）
//最后返回返回根据前序遍历序列和中序遍历序列构造的二叉树序列即可。
public class UsePreorderAndInorderCreateTree {
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public int preIndex;

    public TreeNode buildTree(int[] preorder,int[] inorder) {

        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }

    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd) {
        //这种情况表示当前root没有子树了
        if (inBegin > inEnd) {
            return null;
        }

        TreeNode root = new TreeNode(preorder[preIndex]);

        int rootIndex = findVal(inorder,inBegin,inEnd,preorder[preIndex]);

        preIndex++;

        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inEnd);

        return root;
    }

    public int findVal(int[] inorder,int inBegin,int inEnd,int val) {
        for (int i = inBegin; i <= inEnd; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
}
